package org.brainstretch.recommend;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/**
 * A generic heap implementation in Java. Stores types sorted by the Comparable<E> interface.
 * @author mrodaitis
 *
 * @param <E>
 */
public class Heap<E extends Comparable<E>> {

	ArrayList<E> heap;
	
	/**
	 * Default constructor. Makes a new Heap
	 */
	public Heap(){
		heap = new ArrayList<E>();
	}
	
	/**
	 * Inserts a value into the heap
	 * @param value - the value to be inserted
	 */
	public void insert(E value){
		heap.add(value);
		siftUp(heap.size()-1);
	}
	
	/**
	 * Inserts a collection of elements at once, then turns the structure into a heap.
	 * @param values - the collection of values to be inserted
	 */
	public void insert(Collection<E> values){
		for(E value: values){
			heap.add(value);
		}
		heapify();
	}
        
	/**
	 * Removes the top element of the heap and returns it
	 * @return - the top of the heap at the time remove() was called
	 */
	public E remove(){
		E removed = null;
		if(!heap.isEmpty()){
			removed = top();
			heap.set(0, heap.get(size()-1));
			heap.remove(size()-1);
			siftDown(0);
		}
		return removed;
	}
	
	/**
	 * Returns the item at the top of the heap
	 * @return - the heap at index 0
	 */
	public E top(){
		E top = null;
		if(!heap.isEmpty()){
			top = heap.get(0);
		}
		return top;
	}
	
	/**
	 * Method to access the number of elements in the heap
	 * @return - the current size of the heap
	 */
	public int size(){
		return heap.size();
	}
	
	/**
	 * Turns the elements in the structure into a heap. Used after multiple additions.
	 */
	private void heapify(){
		int index = (size()-2)/2;
		while(index >= 0){
			siftDown(index--);
		}
	}
	
	/**
	 * Moves the element at the given position up as far as it can go in the heap
	 * @param index - the index of the element to be sifted up
	 */
	private void siftUp(int index){
		while(index > 0){
			int parentIndex = (index - 1)/2;
			E parent = heap.get(parentIndex);
			if(parent.compareTo(heap.get(index)) < 0){
				swap(index, parentIndex);
			}
			else{
				index = 0; //Exit the loop when sifting stops
			}
		}
	}
	
	/**
	 * Gets all of the elements in the heap
	 * @return
	 */
	public List<E> getElements(){
		return heap;
	}
	
	/**
	 * Moves the element at the given position down as far as it can go in the heap
	 * @param index - the index of the element to be sifted down
	 */
	private void siftDown(int index){
		while(index <= (size())/2-1){
			int childA = (index+1)*2-1;
			int childB = (index+1)*2;
			int swapIndex = childA;
			if(childB < size() && heap.get(childB).compareTo(heap.get(childA)) > 0){
				swapIndex = childB;
			}
			if(heap.get(swapIndex).compareTo(heap.get(index)) > 0){
				swap(index, swapIndex);
				index = swapIndex;
			}
			else{
				index = size()-1;//Exit the loop when sifting stops
			}
		}
	}
	
	/**
	 * Swaps two elements in the heap
	 * @param indexA - the index of the first element
	 * @param indexB - the index of the second element
	 */
	private void swap(int indexA, int indexB){
		E temp = heap.get(indexA);
		heap.set(indexA, heap.get(indexB));
		heap.set(indexB, temp);
	}
	
}
